This invention relates to recovering spanning trees in computer networks.
A computer network is two or more autonomous computers (or xe2x80x9cend-stationsxe2x80x9d) interconnected by communication links to facilitate the exchange of information. A Local Area Network (LAN) is a network typically implemented within a relatively small geographical area, such as with a factory or college campus. As a practical matter, each LAN has a maximum number of end-stations that it can support. If the practical upper limit of end-stations is approached or exceeded, network performance falls off dramatically. Accordingly, to enable virtually any number of end-stations to communicate with one another over a network, multiple LANs can be connected to each other with bridges (equivalently, gateways or switches).
FIG. 1 shows an example of a structurexe2x80x94referred to as an xe2x80x9cextended LANxe2x80x9d or, equivalently, a xe2x80x9cbridged, multiple segment LANxe2x80x9d xe2x80x94that results from interconnecting LANs. In this example, nine individual LANs (numbered 1-9) are interconnected by ten bridges (lettered A-J). As a result of the bridge interconnections, an end-station on LAN 9, for example, can communicate with end-stations on any of the other eight LANs by routing messages (e.g., communication packets or xe2x80x9cframesxe2x80x9d) as appropriate through one or more of the Bridges A-J. Each bridge that receives a frame forwards it on to the other bridges as appropriate to deliver the message to its intended recipient.
Two basic bridging architectures exist for interconnecting LANs: xe2x80x9csource routingxe2x80x9d and xe2x80x9ctransparent bridging.xe2x80x9d A third bridging architecturexe2x80x94source routing transparent bridgingxe2x80x94is a hybrid of the other two. Source routing transparent bridging is described in ANSI/IEEE Std. 802.1D, 1993 Edition, which is incorporated by reference.
In the source routing architecture, the specific route that a frame is to take through the networkxe2x80x94that is, from the xe2x80x9csourcexe2x80x9d end-station to the xe2x80x9cdestinationxe2x80x9d end-stationxe2x80x94is carried within the frame itself. The routing information in a source routing frame must specify each step along the way from the source end-station to the destination end-station. Accordingly, prior to sending a frame, the sending end-station must have knowledge of the network topology so that a specific xe2x80x9csource routexe2x80x9d can be specified in the frame to be sent. This knowledge of the network topology is obtained by sending a preliminary frame known as an xe2x80x9cexplorer frame,xe2x80x9d which propagates through the network and gathers information about each network bridge and LAN through which it passes. A detailed description of the source routing architecture and related protocols is set forth in IEEE standards such as IEEE 802.1 and IEEE 802.5.
In the transparent bridging architecture, in contrast, routing information for a frame is not carried within the frame and thus need not be known to, or specified by, the source end-station prior to sending a frame. Rather, routing is determined by the destination address of a frame (i.e., the network address of the destination end-station) and by routing tables maintained at each bridge in the network. In particular, each bridge maintains a table that can include the identity of all potential destinations (end-stations) in the network. For each potential destination, a bridge""s routing table identifies an associated xe2x80x9cdestination LANxe2x80x9d xe2x80x94that is, a particular one of the various LANs connected to the bridge that leads to, either directly or indirectly, the specified destination end-station.
When a bridge receives an incoming frame from one of its connected LANs (referred to as the xe2x80x9csource LANxe2x80x9d), the bridge inspects the destination address in the frame and forwards the frame on to the destination LAN specified in the routing table. If, however, the destination LAN is the same as the source LAN, then the frame is discarded. On the other hand, if the destination address specified in the frame is unknown (i.e., not listed in the bridge""s routing table), then the bridge forwards the frame on to all LANs to which it is connected (except for the source LAN)xe2x80x94a process known as xe2x80x9cflooding.xe2x80x9d
A potential consequence of flooding is that, if each physical port in each bridge in the network is allowed to transmit and receive frames, infinite loops are likely to result. Consequently, frames will be cycled through the network perpetually and eventually will clog the network when enough accumulate.
To prevent such infinite loops, a concept known as a xe2x80x9cspanning treexe2x80x9d is employed. In a spanning tree, a loop-free topology is realized by selectively designating physical ports on the bridges as either xe2x80x9cblockingxe2x80x9d or xe2x80x9cforwarding.xe2x80x9d xe2x80x9cForwardingxe2x80x9d ports on a bridge are allowed to pass frames while xe2x80x9cblockingxe2x80x9d ports are prohibited from passing frames on to the LAN connected to the blocked port
FIG. 2 shows an example of a spanning tree that could be used for the network k of FIG. 1. The solid lines between Bridges A-J represent connections between bridge ports that are in forwarding states. These connections form part of the spanning tree for the network. The dotted lines, in contrast, represent connection between bridge ports that are in a blocking state and thus which are not part of the spanning tree for the network.
As an example of spanning tree routing, assume a frame originates at source LAN 8 and is bound for destination LAN 6. Such a frame would be routed according to the spanning tree in FIG. 2 as follows: LAN 8 to Bridge H to LAN 5 to Bridge D to LAN 2 to Bridge B to LAN 3 to Bridge E to LAN 6. Note that the otherwise shorter (lower cost) path through Bridge G is unavailable because Bridge G is not part of the spanning tree. Although in some situations, as in this example, the use of a spanning tree results in a longer path from source to destination, it nevertheless ensures a loop-free topology with connectivity between each end-station.
When a network is first installed, the spanning tree needs to be generated in the first instance. To do so, first the bridges have to choose one bridge that will serve as the root of the tree. Typically, this is accomplished by having each bridge broadcast a special packet referred to as a BPDU (xe2x80x9cBridge Protocol Data Unitxe2x80x9d) packet. The BPDU packet includes the bridge""s serial numberxe2x80x94or MAC (Media Access Control) addressxe2x80x94which is installed by the bridge manufacturer and is guaranteed to be worldwide unique. Then, the bridge having the lowest MAC address is chosen as the root. Next, a spanning tree is constructed from the root to every bridge and LAN in the network based on the least cost path between each LAN, with least cost being related to bandwidth. An algorithm for generating a spanning tree is specified in the IEEE 802.1D standard (1993 ed.), which is incorporated by reference.
Under normal operating conditions, various situations may arise that require the re-generation of a spanning tree. For example, when a network is taken down for whatever reason and then brought back up, the spanning tree must be re-generated before useful network communications can occur. As another example, when a communication failure occurs after the spanning tree already has been generated (e.g., either by a bridge or a communication link failing), the bridges in the network typically will re-run the spanning tree algorithm to build a new spanning tree that reflects the changed network topology. During this re-generation of the spanning tree, which typically takes anywhere between 10 and 50 seconds to complete, no communication between LAN end-stations can occur.
Various implementations of the invention may include one or more of the following features.
In general, in one aspect, a spanning tree is managed (e.g., generated and/or recovered) in a computer network by identifying a network core (e.g., a high bandwidth portion of the computer network), determining a distance to the network core for each switch in the network, and generating and/or recovering a spanning tree for the network based on the switches"" relative distances to the network core. Prior to determining the switches"" respective distances to the network core, the network core is identified as including one or more of the switches in the network. This identification can be based on predetermined priorities associated with switches in the computer network.
In another aspect, management of the spanning tree includes constraining an initial formulation of the spanning tree such that the spanning tree is centered at the network core. The constraints may include choosing a switch residing in the network core as the spanning tree root. Constraining the initial spanning tree formulation also may include propagating through the network information about each switch""s distance to the network core, for example, by broadcasting frames periodically. Each frame can identify the broadcasting switch and a distance-to-core value.
In another aspect, management of the spanning tree includes re covering the spanning tree in response to a communication failure in the computer network. Such recovery of the spanning tree involves reconfiguring a port in a first switch to communicate with another switch closer to the network core. Reconfiguration of the first switch""s port is achieved by changing the port from blocking to forwarding. As a result, recovery of the spanning tree is accomplished without executing a spanning tree generation algorithm.
In another aspect, recovery of the spanning tree includes determining whether a first switch has an operational port for communicating with another switch closer to the network core, and, if an operational port is available, reconfiguring the port to communicate with the other switch. If no operational port is available, the spanning tree generation algorithm may be executed.
In another aspect, upon detecting a spanning tree failure, a switch in a computer network recovers by reconfiguring a port to facilitate communication with another switch that is closer to a network core. The switch detects the spanning tree failure by detecting that a communication failure has occurred on a root port, for example, a port that provides a least cost path to a root of the spanning tree. Reconfiguration of the port may include switching a state of the port from blocking to forwarding.
In another aspect, a spanning tree for a computer network having a plurality of switches is generated by storing in one or more switches in the network a value representing a distance to a network core, and selecting a root for the spanning tree based on the stored distance-to-network-core values. Storage of a distance to network core value may include loading the value into a priority field of a switch ID. Selection of the spanning tree""s root may include selecting as the root a switch having a lowest switch ID, or a switch having a lowest distance-to-network-core value. The distance-to-network-core information may be propagated to each switch in the network, for example, by broadcasting frames periodically, each frame identifying the broadcasting switch and a distance-to-core value.
In another aspect, a network switch residing within a computer network includes a root port in a forwarding state and at least one other port in a blocking state that is connected to another switch in the computer network. The root port can represent a least cost path to a root of a spanning tree for the computer network. The other switch in the network may be closer to the spanning tree""s root. Computer software residing on a computer-readable medium accessible to the switch may include instructions to cause the network switch to perform various operations including detecting a communication failure on the root port, and changing the other port from the blocking state to a forwarding state to facilitate communication with the other switch.
The computer software further may include instructions to determine whether the other switch in the network is closer to the spanning tree""s root prior to changing the state of the other port. The computer software may include instructions to initiate a spanning tree generation algorithm if the other switch in the network is not closer to the spanning tree""s root.
In another aspect, a spanning tree-based computer network includes a plurality of switches one or more of which resides in a network core, and computer software residing on a computer-readable medium at each switch. The software includes instructions to cause a switch to perform various operations including generating, in cooperation with the other switches in the network, a spanning tree for the network by selecting as root one of the switches residing in the network core. In addition, the software includes instructions to cause the switch to recover from a spanning failure by connecting to another switch in the network that is closer to the network core.
The invention may provide one or more of the following advantages. By using certain spanning tree configuration parameters, information about each bridge""s distance to the network""s corexe2x80x94the portion of the network that supports the highest bandwidthxe2x80x94can be propagated throughout the network. As a result, each bridge in the network possesses sufficient knowledge of the network topology to be able instantaneously to reconfigure its ports as appropriate (e.g., from blocking to forwarding or vice versa) to create a modified, loop-free spanning tree.
In this manner, when a communication failure occurs a spanning tree can be recovered quickly and easily without having to re-run the spanning tree algorithm. Consequently, network communications can continue virtually uninterrupted even following a communication failure of the type that, in conventional networks, ordinarily would require the spanning tree algorithm to be re-run from scratch. Moreover, because the spanning tree algorithm need not be re-run necessarily for each communication failure experienced in the network, the waiting period during which end-stations are unable to communicate with each other essentially is eliminated.
As a consequence of requiring a system administrator to use certain spanning tree configuration parameters, the spanning tree is guaranteed to be centered at the network""s core. In a core-centered spanning tree, the speed and efficiency of communications in the network are enhanced dramatically.